[Coding010] DataStructure & LeetCode 206 & 92

单链表的Java实现 & Reverse Linked List Ⅰ&Ⅱ

More coding records

Get the knowledge flowing and circulating! :)

目录

单链表 · Java

Java中单链表的实现，需要先定义一个类，ListNode

链表节点的类定义

※单链表的结点类定义（简单版本）

xxxxxxxxxx
6
1
class ListNode
2
{
3
    int val;
4
    ListNode next;
5
    ListNode(int x) { val = x;}  
6
}

※单链表的结点类定义（复杂版本）

xxxxxxxxxx
28
1
public class ListNode {
2
    
3
    // 成员变量
4
    int val;
5
    ListNode next;
6
    
7
    // 成员函数（构造函数）
8
    /* 
9
     * 在一个类中可以定义多个构造函数，以便提供不同的初始化的方法，供用户选用。
10
     * 这些构造函数具有相同的名字，而参数的个数或参数的类型不相同。
11
     * 这称为构造函数的重载。
12
     */
13
    // 第1个构造函数：无参构造函数
14
    ListNode() {}
15
    
16
    // 第2个构造函数：1个参数的构造函数
17
    ListNode(int val) 
18
    {
19
        this.val = val;
20
    }
21
    
22
    // 第3个构造函数：2个参数的构造函数
23
    ListNode(int val, ListNode next)
24
    {
25
        this.val = val;
26
        this.next = next;
27
    }
28
}

代码解释：

因为Java中没有指针，而对于一个结点而言，需要有指向自身的一种数据类型，所以，这里的类类型就嵌套使用自身。

xxxxxxxxxx
7
1
public class ListNode {
2

3
    // 成员变量
4
    int val;
5
    ListNode next;
6
 // ...
7
}

Demo测试链表

Demo 链表的基本输出(Java小例子 · 完整可运行)

xxxxxxxxxx
38
1
package prj_test;
2

3
class ListNode
4
{
5
    int val;
6
    ListNode next;
7
    ListNode(int x) { val = x;}
8
}
9

10
public class name_test {
11

12
    public static void main(String[] args) {
13
        // TODO Auto-generated method stub
14
        
15
        ListNode l1 = new ListNode(11);  // 定义一个结点，value是11，next为空；
16
        ListNode l2 = new ListNode(22);  // 定义一个结点，value是22，next为空；
17
        ListNode l3 = new ListNode(33);  // 定义一个结点，value是33，next为空；
18
        
19
        l1.next = l3;  // 连接起来：11 → 33 → null
20
        l3.next = l2;  // 连接起来：11 → 33 → 22 → null
21
        
22
        ListNode p = l1;  // p == l1，也就是p指向l1
23
        
24
        while(p != null)
25
        {
26
            // print instead of println, so there is no newline
27
            System.out.print(p.val + " "); 
28
            p = p.next;
29
        }
30
        System.out.println();       
31
        System.out.println("hello, eclipse!");
32
    }
33
}
34
/* output */
35
/* 
36
11 33 22 
37
hello, eclipse!
38
*/

代码解读：

这里是可以运行的java链表小例子，可以看到链表中结点的定义和使用方法。

重点要关注链表中的头结点。

链表的整体反转 206. Reverse Linked List

xxxxxxxxxx
74
1
package prj_test;
2

3
class ListNode
4
{
5
    int val;
6
    ListNode next;
7
    ListNode(int x) { val = x;}
8
}
9

10
class Solution
11
{
12
    public ListNode reverseList(ListNode l)
13
    {
14
        ListNode dummy = new ListNode(0);  // 伪头结点
15

16
        if (l == null) 
17
            return dummy.next;
18

19
        while (l != null)
20
        {
21
            ListNode p = l;  // 取一个节点
22
            l = l.next; // l后移，方便后面再取
23
            
24
            // 下面两步，完成头插
25
            p.next = dummy.next;
26
            dummy.next = p;         
27
        }
28

29
        return dummy.next;
30
    }
31
}
32

33
public class name_test {
34

35
    public static void main(String[] args) {
36
        // TODO Auto-generated method stub
37

38
        ListNode l1 = new ListNode(11);
39
        ListNode l2 = new ListNode(22);
40
        ListNode l3 = new ListNode(33);
41
        ListNode l4 = new ListNode(44);
42
        ListNode l5 = new ListNode(55);
43
        ListNode l6 = new ListNode(66);
44
        ListNode l7 = new ListNode(77);
45

46
        l1.next = l2;
47
        l2.next = l3;
48
        l3.next = l4;
49
        l4.next = l5;
50
        l5.next = l6;
51
        l6.next = l7;
52

53
        ListNode p = l1;
54

55
        while(p != null)
56
        {
57
            System.out.print(p.val + " ");
58
            p = p.next;
59
        }
60
        System.out.println();
61

62
        ListNode res = new Solution().reverseList(l1);
63

64
        ListNode q = res;
65
        while(q != null)
66
        {
67
            System.out.print(q.val + " ");
68
            q = q.next;
69
        }
70
        System.out.println();
71

72
    }
73

74
}

这里是整体把链表翻转过来，采用头插法和尾插法均可。

注意dummy头结点。以及指针的链接。

重点：要找到待操作结点的前一个结点。

链表的局部反转 92. Reverse Linked List II

xxxxxxxxxx
83
1
package prj_test;
2

3

4
class ListNode
5
{
6
    int val;
7
    ListNode next;
8
    ListNode(int x) { val = x;}
9
}
10

11
class Solution
12
{   
13
    public ListNode reversePartList(ListNode l, int left, int right)
14
    {
15
        ListNode p = l;
16

17
        int s = 0;
18
        
19
        // 找到待反转序列的第1个Node之前的Node（链表操作必须）
20
        while(p != null && s < left - 1)  
21
        {
22
            s = s + 1;
23
            p = p.next;
24
        }
25
        
26
        // 对待反转的segment进行单独操作（指针单独定位）
27
        ListNode q = p.next;  // q指向待操作链表部分的首结点
28
        
29
        for (int i = left; i < right; i++)
30
        {
31
            ListNode r = q.next; // r指向首结点的下一个结点
32
            
33
            // 防止链表断裂（现在就可以放心的把r单独提取出来了）
34
            q.next = r.next;    // 为放心地取用r结点作准备（可以取r结点了）
35
            r.next = p.next;    // 操作r的后继
36
            p.next = r;         // 操作r的前驱
37
        }
38
        
39
        return l;
40
    }
41
}
42

43
public class name_test {
44

45
    public static void main(String[] args) {
46
        // TODO Auto-generated method stub
47
        ListNode dummy = new ListNode(0);
48
        
49
        ListNode l1 = new ListNode(11);
50
        ListNode l2 = new ListNode(22);
51
        ListNode l3 = new ListNode(33);
52
        ListNode l4 = new ListNode(44);
53
        ListNode l5 = new ListNode(55);
54
        ListNode l6 = new ListNode(66);
55
        ListNode l7 = new ListNode(77);
56
        
57
        dummy.next = l1;
58
        l1.next = l2;
59
        l2.next = l3;
60
        l3.next = l4;
61
        l4.next = l5;
62
        l5.next = l6;
63
        l6.next = l7;
64
        
65
        ListNode res = new Solution().reversePartList(dummy, 2, 4);
66
        
67
        ListNode iter = res.next;
68
        while(iter != null)
69
        {
70
            System.out.print(iter.val + " ");
71
            iter = iter.next;
72
        }
73
        System.out.println();
74
    }
75
}
76

77
/* input:
78
    2 4
79
*/
80

81
/* output:
82
    11 44 33 22 55 66 77 
83
*/

重点还是一样：要找到待操作结点前面的一个结点。才能让链表不断！

必会单词

dummy / ˈdʌmi /

• n.人体模型，假人（常用于陈列服装）；（练习或训练中用的）仿制品，仿造物；玩具娃娃，玩偶；沉默的人；挂名者，虚设者，傀儡；<非正式>笨蛋，蠢人；（主要指橄榄球及英式足球中的）假传球（或踢球）动作；<英>橡皮（或塑料）奶头，橡皮奶嘴；（桥牌中的）明手牌；（惠斯特牌戏中的）虚拟搭档；（尤指版面的）空白样本（或样张），（书的）装帧样本；空包弹；（语法）假代的，形式的（只有语法功能而无语义的）

• adj.假的，仿真的

• v.（主要指橄榄球及英式足球中的）假传球（或踢球）动作

例句：

Dummy text is a veil between you and reality.

虚拟文字是隔在你和现实之间的面纱。